package com.xcc.dataStructures.leetcode;

/**
 * 给定一个非负整数数组，你最初位于数组的第一个位置。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度(最大長度)。
 * 判断你是否能够到达最后一个位置。
 * <p>
 * 示例 1:
 * 输入: [2,3,1,1,4]
 * 输出: true
 * 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
 * <p>
 * 示例 2:
 * 输入: [3,2,1,0,4]
 * 输出: false
 * 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jump-game
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Demo011_JumpGame {

    public static boolean getJump(int[] arr) {
        int length = arr.length;
        if (arr[0] == 0) {
            return false;
        }
        for (int i = length -2 ; i > 0  ; ) {
            int now = arr[i];
            //当前值为0
            if (now == 0) {
                for (int j = i; j >= 0 ; j--) {
                    if (arr[j]> i-j ) {
                        i = j;
                        break;
                    }else if (j == 0){
                        return false;
                    }
                }
            }
            i--;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr = {2,3,1,1,0};
        System.out.println(getJump(arr));
    }

    /**
     * 从后往前找，碰到0就找能跳过0的那一步，如果始终不能跳过就为false
     */
    public static boolean canJump1(int[] nums) {
        if (nums.length <= 1) {
            return true;
        }
        //从倒数第二步开始计算，从后往前
        int i = nums.length - 1;
        int tempIndex ;
        int tempStep ;
        while ( i > 0) {
            int step = nums[--i];
            //如果当前这一步为0,那麽他的前面多少步必须大于这个步数
            if (step == 0) {
                //记录是否走出了当前这一步
                boolean flag = false;
                tempIndex = i; //记录当前索引值
                while (i > 0) {
                    tempStep = nums[--i];
                    if (tempStep  > (tempIndex-i)) {
                        flag = true;
                        break;
                    }
                }
                if (i==0 && !flag) {
                    return false;
                }
            }
        }
        return true;
    }

    public static boolean canJump(int[] nums) {
//        int[] arr = {3,3,1,5,1,4};
        Jump jump = new Jump(nums);
        jump.check(0, 0);
        return jump.flag;
    }


}

class Jump {
    //判断最终是否能成功
    boolean flag = false;
    //记录当前数组
    private int[] arr;

    public Jump(int[] arr) {
        this.arr = arr;
    }

    /**
     * 算法核心
     *
     * @param cur  当前所在的索引
     * @param step 步数
     */
    public void check(int cur, int step) {
        //表示满足条件
        if (cur + step == arr.length - 1) {
            flag = true;
            return;
        }
        //如果步数操出，则直接退出
        if (cur + step > arr.length - 1) {
            flag = true;
            return ;
        }
        //获取当前步数
        int len = arr[cur + step];
        for (int i = len; i > 0; i--) {
            //如果当前已经为true，可直接退出循环
            if (flag) {
                return;
            }
            check(cur + step, i);
        }
    }

}
